home *** CD-ROM | disk | FTP | other *** search
/ PC-Blue - MS DOS Public Domain Library / PC-Blue MS-DOS Public Domain Library - NYACC.iso / vol350 / prolog.arc / PUZZLES.ARC / MISCAN.PRO < prev    next >
Encoding:
Text File  |  1986-07-20  |  6.5 KB  |  168 lines
  1.      /*             Missionary-cannibal-boat problem
  2.  
  3.      Three missionaries and three cannibals meet at the south bank of
  4.      a river.  A boat, capable of holding one rower and one passenger,
  5.      is tied to the bank.  All persons wish to cross to the other side
  6.      (the north bank) of the river.
  7.  
  8.      A complicating factor is that, should the cannibals outnumber the
  9.      missionaries on either bank or in the boat, the cannibals will
  10.      kill and eat the missionaries.  This is a situation that the
  11.      missionaries, not all that sure of their eternal deliverance,
  12.      fervently wish to avoid.
  13.  
  14.      The code below generates a solution to the problem.
  15.  
  16.      The problem solving process is initiated by the statement
  17.  
  18.                     solvex(statex(0,0,3,3,south),[]).
  19.  
  20.      where the predicate statex is described below and the []
  21.      represents the initially empty solution list of states.
  22.  
  23.      The predicate statex gives the circumstances after each 'move' of
  24.      the problem.  It is defined as:
  25.  
  26.                     statex(#missionaries on north shore,
  27.                            #cannibals on north shore,
  28.                            #missionaries on south shore,
  29.                            #cannibals on south shore,
  30.                            shore on which boat resides)
  31.  
  32.      The other predicates used in this solution of the problem are:
  33.  
  34.           predicate                     description
  35.           *********           *******************************************
  36.  
  37.           movex               generates a new move from the current state
  38.  
  39.           goodx               tests a state to see if it is an 'allowed'
  40.                               state, i.e. determines that the number of
  41.                               missionaries on each shore is greater than
  42.                               the number of cannibals on that shore.
  43.  
  44.           member              tests a state to see if it has been used
  45.                               before, i.e., prevents a logical loop.
  46.  
  47.           prt                 prints the final list of the states traversed
  48.                               to reach the problem solution.
  49.     \*
  50.      The following predicate must be first.                      */
  51.  
  52.      solvex(statex(3,3,0,0,north),Print_list) :-   prt(Print_list),!.
  53.      /*
  54. .PA
  55.           This predicate accepts the initial state and starts the
  56.           problem solving process.                               */
  57.  
  58.      solvex(statex(0,0,3,3,south),[]) :-
  59.           movex(statex(0,0,3,3,south),statex(Mmn,Mcn,Mms,Mcs,north)),
  60.           goodx(statex(Mmn,Mcn,Mms,Mcs,north)),
  61.           solvex(statex(Mmn,Mcn,Mms,Mcs,north),
  62.                         [[Mmn,Mcn,Mms,Mcs,north],[0,0,3,3,south]]).
  63.  
  64.      /*   The predicate below does most of the work - it accepts the
  65.           current state and generates a new move in the puzzle.  */
  66.  
  67.      solvex(statex(Missionary_north, Cannibal_north,
  68.                    Missionary_south, Cannibal_south, Shore),
  69.                    List) :-
  70.           movex(statex(Missionary_north, Cannibal_north,
  71.                        Missionary_south, Cannibal_south, Shore),
  72.                 statex(Mmn,Mcn,Mms,Mcs,Sh)),
  73.           goodx(statex(Mmn,Mcn,Mms,Mcs,Sh)),
  74.           not(member([Mmn,Mcn,Mms,Mcs,Sh],List)),
  75.           solvex(statex(Mmn,Mcn,Mms,Mcs,Sh),
  76.                        [[Mmn,Mcn,Mms,Mcs,Sh]|List]).
  77.  
  78.      /*   The good states (for the missionaries) are given below  */
  79.  
  80.      goodx(statex(Mmn,Mcn,Mms,Mcs,_)) :- (Mmn >= Mcn), (Mms >= Mcs),
  81.                                          (Mmn >= 0),   (Mms >= 0),
  82.                                          (Mcn >= 0),   (Mcs >= 0).
  83.  
  84.      goodx(statex(Mmn,Mcn,Mms,Mcs,_)) :- (Mmn = 0),  (Mms >= 0),
  85.                                          (Mcs >= 0), (Mcn >= 0).
  86.  
  87.      goodx(statex(Mmn,Mcn,Mms,Mcs,_)) :- (Mms = 0),  (Mmn >= 0),
  88.                                          (Mcs >= 0), (Mcn >= 0).
  89.      /*
  90.           The possible moves are given below.  Start with
  91.           north to south moves of missionaries.                  */
  92.  
  93.      movex(statex(Mmn,Mcn,Mms,Mcs,north),
  94.            statex(Nmn,Ncn,Nms,Ncs,south)) :-
  95.            Nmn is Mmn - 2, Nms is Mms + 2,
  96.            Ncn is Mcn, Ncs is Mcs.
  97.  
  98.      movex(statex(Mmn,Mcn,Mms,Mcs,north),
  99.            statex(Nmn,Ncn,Nms,Ncs,south)) :-
  100.            Nmn is Mmn - 1, Nms is Mms + 1,
  101.            Ncn is Mcn, Ncs is Mcs.
  102.  
  103.      /*
  104. .PA
  105.               Now define the north to south moves of cannibals.      */
  106.  
  107.      movex(statex(Mmn,Mcn,Mms,Mcs,north),
  108.            statex(Nmn,Ncn,Nms,Ncs,south)) :-
  109.            Ncn is Mcn - 2, Ncs is Mcs + 2,
  110.            Nmn is Mmn, Nms is Mms.
  111.  
  112.      movex(statex(Mmn,Mcn,Mms,Mcs,north),
  113.            statex(Nmn,Ncn,Nms,Ncs,south)) :-
  114.            Ncn is Mcn - 1, Ncs is Mcs + 1,
  115.            Nmn is Mmn, Nms is Mms.
  116.  
  117.      /*   Now define north to south moves via an integrated boat.*/
  118.  
  119.      movex(statex(Mmn,Mcn,Mms,Mcs,north),
  120.            statex(Nmn,Ncn,Nms,Ncs,south)) :-
  121.            Nmn is Mmn - 1, Nms is Mms + 1,
  122.            Ncn is Mcn - 1, Ncs is Mcs + 1.
  123.  
  124.      /*   Now define all the south to north moves.  Start with
  125.           south to north moves of missionaries.                  */
  126.  
  127.      movex(statex(Mmn,Mcn,Mms,Mcs,south),
  128.            statex(Nmn,Ncn,Nms,Ncs,north)) :-
  129.            Nmn is Mmn + 2, Nms is Mms - 2,
  130.            Ncn is Mcn, Ncs is Mcs.
  131.  
  132.      movex(statex(Mmn,Mcn,Mms,Mcs,south),
  133.            statex(Nmn,Ncn,Nms,Ncs,north)) :-
  134.            Nmn is Mmn + 1, Nms is Mms - 1,
  135.            Ncn is Mcn, Ncs is Mcs.
  136.      /*
  137.           Now define the south to north moves of cannibals.      */
  138.  
  139.      movex(statex(Mmn,Mcn,Mms,Mcs,south),
  140.            statex(Nmn,Ncn,Nms,Ncs,north)) :-
  141.            Ncn is Mcn + 2, Ncs is Mcs - 2,
  142.            Nmn is Mmn, Nms is Mms.
  143.  
  144.      movex(statex(Mmn,Mcn,Mms,Mcs,south),
  145.            statex(Nmn,Ncn,Nms,Ncs,north)) :-
  146.            Ncn is Mcn + 1, Ncs is Mcs - 1,
  147.            Nms is Mms, Nmn is Mmn.
  148.      /*
  149. .PA
  150.           Now define south to north moves via an integrated boat.*/
  151.  
  152.      movex(statex(Mmn,Mcn,Mms,Mcs,south),
  153.            statex(Nmn,Ncn,Nms,Ncs,north)) :-
  154.            Nmn is Mmn + 1, Nms is Mms - 1,
  155.            Ncn is Mcn + 1, Ncs is Mcs - 1.
  156.  
  157.      /* The member predicate definition                          */
  158.  
  159.      member(X,[X|_]).
  160.      member(X,[_|L]) :- member(X,L).
  161.  
  162.      /* Predicate to print the final result                      */
  163.  
  164.      prt([]) :- nl.
  165.      prt([X|L]) :- write(X),nl,prt(L).
  166.  
  167.      /* End of predicate definition                              */
  168.